Left Termination of the query pattern d_in_3(g, g, a) w.r.t. the given Prolog program could successfully be proven:



Prolog
  ↳ PrologToPiTRSProof

Clauses:

d(X, X, 1).
d(T, X, 0) :- isnumber(T).
d(times(U, V), X, +(times(B, U), times(A, V))) :- ','(d(U, X, A), d(V, X, B)).
d(div(U, V), X, W) :- d(times(U, power(V, p(0))), X, W).
d(power(U, V), X, times(V, times(W, power(U, p(V))))) :- ','(isnumber(V), d(U, X, W)).
isnumber(0).
isnumber(s(X)) :- isnumber(X).
isnumber(p(X)) :- isnumber(X).

Queries:

d(g,g,a).

We use the technique of [30]. With regard to the inferred argument filtering the predicates were used in the following modes:
d_in: (b,b,f)
isnumber_in: (b)
Transforming Prolog into the following Term Rewriting System:
Pi-finite rewrite system:
The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X, 0) → U1_gga(T, X, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X, isnumber_out_g(T)) → d_out_gga(T, X, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)

Infinitary Constructor Rewriting Termination of PiTRS implies Termination of Prolog



↳ Prolog
  ↳ PrologToPiTRSProof
PiTRS
      ↳ DependencyPairsProof

Pi-finite rewrite system:
The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X, 0) → U1_gga(T, X, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X, isnumber_out_g(T)) → d_out_gga(T, X, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)


Using Dependency Pairs [1,30] we result in the following initial DP problem:
Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(T, X, 0) → U1_GGA(T, X, isnumber_in_g(T))
D_IN_GGA(T, X, 0) → ISNUMBER_IN_G(T)
ISNUMBER_IN_G(s(X)) → U7_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → U8_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → U4_GGA(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → ISNUMBER_IN_G(V)
U5_GGA(U, V, X, W, isnumber_out_g(V)) → U6_GGA(U, V, X, W, d_in_gga(U, X, W))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → U3_GGA(U, V, X, B, A, d_in_gga(V, X, B))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X, 0) → U1_gga(T, X, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X, isnumber_out_g(T)) → d_out_gga(T, X, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
U6_GGA(x1, x2, x3, x4, x5)  =  U6_GGA(x1, x2, x5)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U3_GGA(x1, x2, x3, x4, x5, x6)  =  U3_GGA(x1, x2, x5, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x5)
U8_G(x1, x2)  =  U8_G(x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x3)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U7_G(x1, x2)  =  U7_G(x2)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)

We have to consider all (P,R,Pi)-chains

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
PiDP
          ↳ DependencyGraphProof

Pi DP problem:
The TRS P consists of the following rules:

D_IN_GGA(T, X, 0) → U1_GGA(T, X, isnumber_in_g(T))
D_IN_GGA(T, X, 0) → ISNUMBER_IN_G(T)
ISNUMBER_IN_G(s(X)) → U7_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → U8_G(X, isnumber_in_g(X))
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
D_IN_GGA(div(U, V), X, W) → U4_GGA(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → ISNUMBER_IN_G(V)
U5_GGA(U, V, X, W, isnumber_out_g(V)) → U6_GGA(U, V, X, W, d_in_gga(U, X, W))
U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → U3_GGA(U, V, X, B, A, d_in_gga(V, X, B))
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X, 0) → U1_gga(T, X, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X, isnumber_out_g(T)) → d_out_gga(T, X, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
U6_GGA(x1, x2, x3, x4, x5)  =  U6_GGA(x1, x2, x5)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U3_GGA(x1, x2, x3, x4, x5, x6)  =  U3_GGA(x1, x2, x5, x6)
U4_GGA(x1, x2, x3, x4, x5)  =  U4_GGA(x5)
U8_G(x1, x2)  =  U8_G(x2)
U1_GGA(x1, x2, x3)  =  U1_GGA(x3)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)
U7_G(x1, x2)  =  U7_G(x2)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)

We have to consider all (P,R,Pi)-chains
The approximation of the Dependency Graph [30] contains 2 SCCs with 8 less nodes.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
PiDP
                ↳ UsableRulesProof
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X, 0) → U1_gga(T, X, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X, isnumber_out_g(T)) → d_out_gga(T, X, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
ISNUMBER_IN_G(x1)  =  ISNUMBER_IN_G(x1)

We have to consider all (P,R,Pi)-chains
For (infinitary) constructor rewriting [30] we can delete all non-usable rules from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
PiDP
                    ↳ PiDPToQDPProof
              ↳ PiDP

Pi DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)

R is empty.
Pi is empty.
We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
                ↳ UsableRulesProof
                  ↳ PiDP
                    ↳ PiDPToQDPProof
QDP
                        ↳ QDPSizeChangeProof
              ↳ PiDP

Q DP problem:
The TRS P consists of the following rules:

ISNUMBER_IN_G(s(X)) → ISNUMBER_IN_G(X)
ISNUMBER_IN_G(p(X)) → ISNUMBER_IN_G(X)

R is empty.
Q is empty.
We have to consider all (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs:



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
PiDP
                ↳ PiDPToQDPProof

Pi DP problem:
The TRS P consists of the following rules:

U5_GGA(U, V, X, W, isnumber_out_g(V)) → D_IN_GGA(U, X, W)
D_IN_GGA(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_GGA(U, V, X, W, isnumber_in_g(V))
D_IN_GGA(div(U, V), X, W) → D_IN_GGA(times(U, power(V, p(0))), X, W)
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → U2_GGA(U, V, X, B, A, d_in_gga(U, X, A))
D_IN_GGA(times(U, V), X, +(times(B, U), times(A, V))) → D_IN_GGA(U, X, A)
U2_GGA(U, V, X, B, A, d_out_gga(U, X, A)) → D_IN_GGA(V, X, B)

The TRS R consists of the following rules:

d_in_gga(X, X, 1) → d_out_gga(X, X, 1)
d_in_gga(T, X, 0) → U1_gga(T, X, isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g(0)
isnumber_in_g(s(X)) → U7_g(X, isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(X, isnumber_in_g(X))
U8_g(X, isnumber_out_g(X)) → isnumber_out_g(p(X))
U7_g(X, isnumber_out_g(X)) → isnumber_out_g(s(X))
U1_gga(T, X, isnumber_out_g(T)) → d_out_gga(T, X, 0)
d_in_gga(times(U, V), X, +(times(B, U), times(A, V))) → U2_gga(U, V, X, B, A, d_in_gga(U, X, A))
d_in_gga(div(U, V), X, W) → U4_gga(U, V, X, W, d_in_gga(times(U, power(V, p(0))), X, W))
d_in_gga(power(U, V), X, times(V, times(W, power(U, p(V))))) → U5_gga(U, V, X, W, isnumber_in_g(V))
U5_gga(U, V, X, W, isnumber_out_g(V)) → U6_gga(U, V, X, W, d_in_gga(U, X, W))
U6_gga(U, V, X, W, d_out_gga(U, X, W)) → d_out_gga(power(U, V), X, times(V, times(W, power(U, p(V)))))
U4_gga(U, V, X, W, d_out_gga(times(U, power(V, p(0))), X, W)) → d_out_gga(div(U, V), X, W)
U2_gga(U, V, X, B, A, d_out_gga(U, X, A)) → U3_gga(U, V, X, B, A, d_in_gga(V, X, B))
U3_gga(U, V, X, B, A, d_out_gga(V, X, B)) → d_out_gga(times(U, V), X, +(times(B, U), times(A, V)))

The argument filtering Pi contains the following mapping:
d_in_gga(x1, x2, x3)  =  d_in_gga(x1, x2)
d_out_gga(x1, x2, x3)  =  d_out_gga(x3)
U1_gga(x1, x2, x3)  =  U1_gga(x3)
isnumber_in_g(x1)  =  isnumber_in_g(x1)
0  =  0
isnumber_out_g(x1)  =  isnumber_out_g
s(x1)  =  s(x1)
U7_g(x1, x2)  =  U7_g(x2)
p(x1)  =  p(x1)
U8_g(x1, x2)  =  U8_g(x2)
times(x1, x2)  =  times(x1, x2)
U2_gga(x1, x2, x3, x4, x5, x6)  =  U2_gga(x1, x2, x3, x6)
div(x1, x2)  =  div(x1, x2)
U4_gga(x1, x2, x3, x4, x5)  =  U4_gga(x5)
power(x1, x2)  =  power(x1, x2)
U5_gga(x1, x2, x3, x4, x5)  =  U5_gga(x1, x2, x3, x5)
U6_gga(x1, x2, x3, x4, x5)  =  U6_gga(x1, x2, x5)
U3_gga(x1, x2, x3, x4, x5, x6)  =  U3_gga(x1, x2, x5, x6)
+(x1, x2)  =  +(x1, x2)
U2_GGA(x1, x2, x3, x4, x5, x6)  =  U2_GGA(x1, x2, x3, x6)
U5_GGA(x1, x2, x3, x4, x5)  =  U5_GGA(x1, x2, x3, x5)
D_IN_GGA(x1, x2, x3)  =  D_IN_GGA(x1, x2)

We have to consider all (P,R,Pi)-chains
Transforming (infinitary) constructor rewriting Pi-DP problem [30] into ordinary QDP problem [15] by application of Pi.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ PiDPToQDPProof
QDP
                    ↳ QDPOrderProof

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U2_GGA(U, V, X, d_out_gga(A)) → D_IN_GGA(V, X)
D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)
D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(1)
d_in_gga(T, X) → U1_gga(isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g
U1_gga(isnumber_out_g) → d_out_gga(0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g) → U6_gga(U, V, d_in_gga(U, X))
U6_gga(U, V, d_out_gga(W)) → d_out_gga(times(V, times(W, power(U, p(V)))))
U4_gga(d_out_gga(W)) → d_out_gga(W)
U2_gga(U, V, X, d_out_gga(A)) → U3_gga(U, V, A, d_in_gga(V, X))
U3_gga(U, V, A, d_out_gga(B)) → d_out_gga(+(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)

We have to consider all (P,Q,R)-chains.
We use the reduction pair processor [15].


The following pairs can be oriented strictly and are deleted.


D_IN_GGA(times(U, V), X) → D_IN_GGA(U, X)
D_IN_GGA(times(U, V), X) → U2_GGA(U, V, X, d_in_gga(U, X))
The remaining pairs can at least be oriented weakly.

D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U2_GGA(U, V, X, d_out_gga(A)) → D_IN_GGA(V, X)
D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)
Used ordering: Polynomial interpretation [25]:

POL(+(x1, x2)) = 0   
POL(0) = 0   
POL(1) = 0   
POL(D_IN_GGA(x1, x2)) = 1 + x1 + x2   
POL(U1_gga(x1)) = 0   
POL(U2_GGA(x1, x2, x3, x4)) = 1 + x2 + x3   
POL(U2_gga(x1, x2, x3, x4)) = 0   
POL(U3_gga(x1, x2, x3, x4)) = 0   
POL(U4_gga(x1)) = 0   
POL(U5_GGA(x1, x2, x3, x4)) = 1 + x1 + x3   
POL(U5_gga(x1, x2, x3, x4)) = 0   
POL(U6_gga(x1, x2, x3)) = 0   
POL(U7_g(x1)) = 0   
POL(U8_g(x1)) = 0   
POL(d_in_gga(x1, x2)) = 0   
POL(d_out_gga(x1)) = 0   
POL(div(x1, x2)) = 1 + x1 + x2   
POL(isnumber_in_g(x1)) = 0   
POL(isnumber_out_g) = 0   
POL(p(x1)) = 0   
POL(power(x1, x2)) = x1   
POL(s(x1)) = 0   
POL(times(x1, x2)) = 1 + x1 + x2   

The following usable rules [17] were oriented: none



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ PiDPToQDPProof
                  ↳ QDP
                    ↳ QDPOrderProof
QDP
                        ↳ DependencyGraphProof

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U2_GGA(U, V, X, d_out_gga(A)) → D_IN_GGA(V, X)
D_IN_GGA(div(U, V), X) → D_IN_GGA(times(U, power(V, p(0))), X)
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(1)
d_in_gga(T, X) → U1_gga(isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g
U1_gga(isnumber_out_g) → d_out_gga(0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g) → U6_gga(U, V, d_in_gga(U, X))
U6_gga(U, V, d_out_gga(W)) → d_out_gga(times(V, times(W, power(U, p(V)))))
U4_gga(d_out_gga(W)) → d_out_gga(W)
U2_gga(U, V, X, d_out_gga(A)) → U3_gga(U, V, A, d_in_gga(V, X))
U3_gga(U, V, A, d_out_gga(B)) → d_out_gga(+(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)

We have to consider all (P,Q,R)-chains.
The approximation of the Dependency Graph [15,17,22] contains 1 SCC with 2 less nodes.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ PiDPToQDPProof
                  ↳ QDP
                    ↳ QDPOrderProof
                      ↳ QDP
                        ↳ DependencyGraphProof
QDP
                            ↳ UsableRulesProof

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

d_in_gga(X, X) → d_out_gga(1)
d_in_gga(T, X) → U1_gga(isnumber_in_g(T))
isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g
U1_gga(isnumber_out_g) → d_out_gga(0)
d_in_gga(times(U, V), X) → U2_gga(U, V, X, d_in_gga(U, X))
d_in_gga(div(U, V), X) → U4_gga(d_in_gga(times(U, power(V, p(0))), X))
d_in_gga(power(U, V), X) → U5_gga(U, V, X, isnumber_in_g(V))
U5_gga(U, V, X, isnumber_out_g) → U6_gga(U, V, d_in_gga(U, X))
U6_gga(U, V, d_out_gga(W)) → d_out_gga(times(V, times(W, power(U, p(V)))))
U4_gga(d_out_gga(W)) → d_out_gga(W)
U2_gga(U, V, X, d_out_gga(A)) → U3_gga(U, V, A, d_in_gga(V, X))
U3_gga(U, V, A, d_out_gga(B)) → d_out_gga(+(times(B, U), times(A, V)))

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)

We have to consider all (P,Q,R)-chains.
As all Q-normal forms are R-normal forms we are in the innermost case. Hence, by the usable rules processor [15] we can delete all non-usable rules [17] from R.

↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ PiDPToQDPProof
                  ↳ QDP
                    ↳ QDPOrderProof
                      ↳ QDP
                        ↳ DependencyGraphProof
                          ↳ QDP
                            ↳ UsableRulesProof
QDP
                                ↳ QReductionProof

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g

The set Q consists of the following terms:

d_in_gga(x0, x1)
isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)

We have to consider all (P,Q,R)-chains.
We deleted the following terms from Q as each root-symbol of these terms does neither occur in P nor in R.

d_in_gga(x0, x1)
U1_gga(x0)
U5_gga(x0, x1, x2, x3)
U6_gga(x0, x1, x2)
U4_gga(x0)
U2_gga(x0, x1, x2, x3)
U3_gga(x0, x1, x2, x3)



↳ Prolog
  ↳ PrologToPiTRSProof
    ↳ PiTRS
      ↳ DependencyPairsProof
        ↳ PiDP
          ↳ DependencyGraphProof
            ↳ AND
              ↳ PiDP
              ↳ PiDP
                ↳ PiDPToQDPProof
                  ↳ QDP
                    ↳ QDPOrderProof
                      ↳ QDP
                        ↳ DependencyGraphProof
                          ↳ QDP
                            ↳ UsableRulesProof
                              ↳ QDP
                                ↳ QReductionProof
QDP
                                    ↳ QDPSizeChangeProof

Q DP problem:
The TRS P consists of the following rules:

D_IN_GGA(power(U, V), X) → U5_GGA(U, V, X, isnumber_in_g(V))
U5_GGA(U, V, X, isnumber_out_g) → D_IN_GGA(U, X)

The TRS R consists of the following rules:

isnumber_in_g(0) → isnumber_out_g
isnumber_in_g(s(X)) → U7_g(isnumber_in_g(X))
isnumber_in_g(p(X)) → U8_g(isnumber_in_g(X))
U8_g(isnumber_out_g) → isnumber_out_g
U7_g(isnumber_out_g) → isnumber_out_g

The set Q consists of the following terms:

isnumber_in_g(x0)
U8_g(x0)
U7_g(x0)

We have to consider all (P,Q,R)-chains.
By using the subterm criterion [20] together with the size-change analysis [32] we have proven that there are no infinite chains for this DP problem.

From the DPs we obtained the following set of size-change graphs: